package com.sheng.leetcode.year2022.month12.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/12/22
 * <p>
 * 1799. N 次操作后的最大分数和<p>
 * <p>
 * 给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。<p>
 * 在第 i 次操作时（操作编号从 1 开始），你需要：<p>
 * 选择两个元素 x 和 y 。<p>
 * 获得分数 i * gcd(x, y) 。<p>
 * 将 x 和 y 从 nums 中删除。<p>
 * 请你返回 n 次操作后你能获得的分数和最大为多少。<p>
 * 函数 gcd(x, y) 是 x 和 y 的最大公约数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,2]<p>
 * 输出：1<p>
 * 解释：最优操作是：<p>
 * (1 * gcd(1, 2)) = 1<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [3,4,6,8]<p>
 * 输出：11<p>
 * 解释：最优操作是：<p>
 * (1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [1,2,3,4,5,6]<p>
 * 输出：14<p>
 * 解释：最优操作是：<p>
 * (1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 7<p>
 * nums.length == 2 * n<p>
 * 1 <= nums[i] <= 10^6<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximize-score-after-n-operations">1799. N 次操作后的最大分数和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1799 {

    @Test
    public void test01() {
        int[] nums = {1, 2};
//        int[] nums = {3, 4, 6, 8};
//        int[] nums = {1, 2, 3, 4, 5, 6};
        System.out.println(new Solution().maxScore(nums));
    }
}

class Solution {

    int n, m;
    int[][] dp;

    public int maxScore(int[] nums) {
        /**
         * 思路：对数组进行两两分组
         */
        n = nums.length;
        m = n / 2;
        dp = new int[1 << n][m + 1];
        return dfs(nums, 0, 1);
    }

    int dfs(int[] nums, int cur, int cnt) {
        if (cnt > m) {
            return 0;
        }
        if (dp[cur][cnt] != 0) {
            return dp[cur][cnt];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (((cur >> i) & 1) == 1 || ((cur >> j) & 1) == 1) {
                    continue;
                }
                int next = cur | (1 << i) | (1 << j);
                ans = Math.max(ans, cnt * gcd(nums[i], nums[j]) + dfs(nums, next, cnt + 1));
            }
        }
        dp[cur][cnt] = ans;
        return ans;
    }

    public int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}
